package list;

import java.util.Arrays;

public class MyArrayList<E> {
    private Object[] elementData;
    private int usedSize;
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public MyArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    public MyArrayList(int capacity) {
        if(capacity >= 0){
            this.elementData = new Object[capacity];
        }else{
            throw new IllegalArgumentException("初始化容量小于0");
        }
    }

    public boolean add(E e){
        // 确定真正的容量
        ensureCapacityInternal(usedSize+1);
        elementData[usedSize++] = e;
        return true;
    }
    public void add(int index,E e){
        // 确定真正的容量
        ensureCapacityInternal(usedSize+1);
        copy(index,e);
        usedSize++;
    }
    private void copy(int index,E e){
        for (int i = usedSize-1; i >= index; i--) {
            elementData[i+1] = elementData[i];
        }
        elementData[index] = e;
    }

    private void ensureCapacityInternal(int minCapacity) {
        // 确定需要的容量
        int capacity = calculateCapacity(elementData, minCapacity);
        // 分配容量
        ensureExplicitCapacity(capacity);
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
            return Math.max(10,minCapacity);
        }else{
            return minCapacity;
        }
    }
    private void ensureExplicitCapacity(int minCapacity) {
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity>>1);// 1.5倍扩容
        if(newCapacity - minCapacity < 0){
            newCapacity = minCapacity;
        }
        if(newCapacity - Integer.MAX_VALUE-8 > 0){
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData,newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > Integer.MAX_VALUE-8) ?
                Integer.MAX_VALUE :
                Integer.MAX_VALUE-8;
    }
}
